const common = require('./base/common');

/**
 * 1、按位数1法
 * 注：这里采用(num!=0)主要是为了避免32位整数有负值的情况
 * 
 * @param {*} num 32位整数
 */
function bitcount_m1(num) {
    let count = 0;
    while (num != 0) {
        count += num & 1;
        num >>>= 1;
    }
    return count;
}

/**
 * 2、按1数位法
 * 
 * @param {*} num 32位整数
 */
function bitcount_m2(num) {
    let count = 0;
    while (num != 0) {
        count++;
        num &= (num - 1);
    }
    return count;
}

/**
 * 3、查表法
 * 
 * @param {*} num 32位整数
 */
function bitcount_m3(num) {
    if (!this.searchTable) {
        this.searchTable = [0];
        for (let i = 1; i < 256; ++i) {
            this.searchTable[i] = (i & 0x1) + this.searchTable[i >> 1];
        }
    }

    return this.searchTable[num & 0xff] +
        this.searchTable[(num >> 8) & 0xff] +
        this.searchTable[(num >> 16) & 0xff] +
        this.searchTable[(num >> 24) & 0xff];
}

/**
 * 4、种群算法
 * 
 * @param {*} num 32位整数
 */
function bitcount_m4(num) {
    num = (num & 0x55555555) + ((num >>> 1) & 0x55555555);
    num = (num & 0x33333333) + ((num >>> 2) & 0x33333333);
    num = (num & 0x0f0f0f0f) + ((num >>> 4) & 0x0f0f0f0f);
    num = (num & 0x00ff00ff) + ((num >>> 8) & 0x00ff00ff);
    num = (num & 0x0000ffff) + ((num >>> 16) & 0x0000ffff);
    return num & 0x3f;
}

/**
 * 5、种群算法加强版（Java中bitcount的实现）
 * 公式：population(x) = x - [x/2] - [x/4] -...-[x/(2^32)]
 * 
 * @param {*} num 32位整数
 */
function bitcount_m5(i) {
    // x - [x/2] = i/2
    i = i - ((i >>> 1) & 0x55555555);
    // x + [x/4] = i/2 + i/(2^3)
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    // x + [x/8] = i/2 + i/(2^3) + i/(2^4) + x/(2^5)
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    // x + [x/16] = i/(2^2) + i/(2^7) + i/(2^8) + i/(2^9)
    i = i + (i >>> 8);
    // x + [x/32] = i/(2^2) + i/(2^6) + i/(2^8) + i/(2^9)+ i/(2^12) + i/(2^13) + i/(2^14)
    i = i + (i >>> 16);
    return i & 0x3f;
}

/**
 * 191. 位1的个数(也被称为汉明重量)
 * 
 * Note: 聚合计算，当每种模式结果一样时才输出
 * 
 * @param {*} x 32位整数
 * @returns 多模式结合结果
 */
function hammingWeight(x) {
    let m1 = bitcount_m1(x),
        m2 = bitcount_m2(x),
        m3 = bitcount_m3(x),
        m4 = bitcount_m4(x),
        m5 = bitcount_m5(x);
    return [m1, m2, m3, m4, m5].reduce((a, b) => a === b? b: null);
}

common.testing([
    0b01100110000110010011001011110000,
    0b10011100011100001110000111010010,
    0b01010101010101010110101010101010,
    0b10101010101010101010101010101010,
    0b00000000000000000000000000000001,
    0b10000000000000000000000000000001,
    0b10000000000000000000000000000000,
    0b00000000000000100000000000000000,
    0b00010001000100010001000100010001,
    0xCAFFBABE,
    0x00AD0BE0,
    0xFAFAFAFA,
    0xAFAFAFAF,
    0xAAAAAAAA,
    20210208,
    20200730
], [14, 15, 16, 16, 1, 2, 1, 1, 8, 23, 11, 24, 24, 16, 8, 12])(x => hammingWeight(x));